
class Solution {
    /**
     * 如果选了节点x,就不能选x的left和right
     * 如果没选节点x,则左右节点均能选
     */
    public int rob(TreeNode root) {
        int[] ans = dfs(root);

        return Math.max(ans[0], ans[1]);
    }

    public int[] dfs(TreeNode node) {
        if (node == null)
            return new int[]{0, 0};
        int[] l = dfs(node.left);
        int[] r = dfs(node.right);

        // 选了node 就不能选left right了
        int select = node.val + l[1] + r[1];
        // 没选node 对于left可以选也可以不选 right同理
        int noSelect = Math.max(l[0], l[1]) + Math.max(r[0], r[1]);

        return new int[]{select, noSelect};
    }
}